package com.itheima

object Queen {
  def main(args: Array[String]): Unit = {
    queueQ(8)
  }

  /**
    * 八皇后问题
    */
  def queueQ(size: Int): Unit = {
    // 没有皇后使用+号表示，使用o表示皇后
    val arr = for (i <- 1 to size) yield for (j <- 1 to size) yield "+"
    var totalMatch = 0

    // 保存皇后的位置
    var queueIndex = new Array[Int](size)
    queueIndex = queueIndex.map(x => -1)

    // 检查放置在该行列位置，是否会被其他皇后吃掉
    def checkIsSafe(row: Int, col: Int): Boolean = {
      // 检查行内是否有皇后
      if (queueIndex(row) != -1) {
        //println(s"第${row}行上有皇后")
        return false
      }

      // 检查列内是否有皇后
      for (tempRow <- 0 until row) {
        val tempCol = queueIndex(tempRow)
        if (tempCol == col) {
          //println(s"第${tempCol}列上有皇后")
          return false
        }
      }

      // 检查左对角线内是否有皇后
      var i = row - 1
      var j = col - 1
      while(i >= 0 && j >= 0) {
        if(queueIndex(i) == j) {
          //println("左对角线有皇后")
          return false
        }
        i-=1
        j-=1
      }

      // 检查右对角线内是否有皇后
      i = row - 1
      j = col + 1
      while(i >= 0 && j <= size - 1) {
        if(queueIndex(i) == j) {
          //println("右对角线有皇后")
          return false
        }
        i-=1
        j+=1
      }

      return true
    }

    def place(row: Int): Unit = {
      if (row == size) {
        for(i <- 0 until size) {
          for(j <- 0 until size) {
            if(queueIndex(i) == j) print(" W ") else print(" + ")
          }
          println
        }
        println

        totalMatch+=1

        return
      }

      // 先放置一个位置
      for (col <- 0 until size) {
        // 判断放在row,col位置是否会被其他皇后吃掉
        val r: Boolean = checkIsSafe(row, col)
        if (r) {
          queueIndex(row) = col
          place(row + 1)
          queueIndex(row) = -1
        }
      }
    }

    place(0)
    println(s"一共${totalMatch}种方案")
  }

}
